// 键值对
class Pair {
    constructor(key, val) {
        this.key = key;
        this.val = val;
    }
}

// 哈希表(单个键值对)
class ArrayHashTable {
    constructor(size) {

        if(typeof size === "undefined"){
            throw new Error('请设置size属性')
        }
        
        if (size < 0) {
            throw new Error("不可以设置小于0的容器大小");
        }
        // 当前数组大小
        Object.defineProperty(this, 'size', {
            get() {
                return size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        function hashFun(key) {
            return key % size;
        }

        // 初始化数组
        let _store = new Array(size);
        /**
         * 获取指定key对应的val
         * 时间复杂度：O(1)
         * @param key
         */
        this.get = function (key) {
            let index = hashFun(key);
            if (_store[index] != null && _store[index].key == key) {
                return _store[index].val;
            }
            return null;
        }
        /**
         * 设置键值对
         * 时间复杂度：O(1)
         * @param key
         * @param ele
         */
        this.set = function (key, ele) {
            let index = hashFun(key);
            _store[index] = new Pair(key, ele);
        }
        /**
         * 删除键
         * 时间复杂度：O(1)
         * @param key
         */
        this.delete = function (key) {
            let index = hashFun(key);
            _store[index] = null;
        }
        /**
         * 获取所有的键值对
         * 时间复杂度：O(n)
         */
        this.entries = function () {
            let result = [];
            for (var i = 0; i < _store.length; i++) {
                if (_store[i] != null) {
                    result.push(_store[i]);
                }
            }
            return result;
        }
        /**
         * 获取所有的键
         * 时间复杂度：O(n)
         */
        this.keys = function () {
            let result = [];
            for (var i = 0; i < _store.length; i++) {
                if (_store[i] != null) {
                    result.push(_store[i].key);
                }
            }
            return result;
        }
        /**
         * 获取所有的值
         * 时间复杂度：O(n)
         */
        this.values = function () {
            let result = [];
            for (var i = 0; i < _store.length; i++) {
                if (_store[i] != null) {
                    result.push(_store[i].val);
                }
            }
            return result;
        }
    }
}

// 哈希表
class HashTableChaining {
    constructor() {
        let _size = 0;
        let capacity = 4;
        // 触发扩容的负载因子
        let loadThres = 2.0 / 3.0;
        let extendRatio = 2;
        // 初始化数组
        let _store = new Array(capacity);

        // 计算哈希值
        function hashFun(key) {
            return key % capacity;
        }

        // 获取指定key对应的val
        this.get = function (key) {
            let index = hashFun(key);
            if (_store[index] != null) {
                for (let i = 0; i < _store[index].length; i++) {
                    if (_store[index][i].key == key) {
                        return _store[index][i].val;
                    }
                }
            }
            return null;
        }

        // 计算当前的负载因子
        function loadFactor () {
            return _size / capacity;
        }

        // 扩容
        this.extend = function () {
            let oldStore = _store;
            capacity = capacity * extendRatio
            let newStore = new Array(capacity);
            for (let row = 0; row < oldStore.length; row++) {
                if (oldStore[row] != null) {
                    for (let colum = 0; colum < oldStore[row].length; colum++) {
                        let ele = oldStore[row][colum];
                        // 计算新的hash
                        let index = hashFun(ele.key);
                        if (newStore[index] == null) {
                            newStore[index] = [];
                        }
                        // 把元素存放到新的hashMap中
                        newStore[index].push(ele);
                    }
                }
            }
            _store = newStore;
        }

        // 设置键值对
        this.set = function (key, ele) {
            if (loadFactor() > loadThres) {
                this.extend();
            }
            let row = hashFun(key);
            let keyEle = new Pair(key, ele);
            if (_store[row] != null) {
                for (let colum = 0; colum < _store[row].length; colum++) {
                    if (_store[row][colum] != null && _store[row][colum].key == key) {
                        // 找到就更新并退出
                        _store[row][colum] = keyEle;
                        return;
                    }
                }
                _size++;
                // 没找到就新增
                _store[row].push(keyEle);
            } else {
                _size++;
                _store[row] = []
                _store[row].push(keyEle);
            }
        }

        // 删除键
        this.delete = function (key) {
            let index = hashFun(key);
            if (_store[index] != null) {
                for (let i = 0; i < _store[index].length; i++) {
                    if (_store[index][i] != null && _store[index][i].key == key) {
                        _store[index].splice(i, 1);
                        _size--;
                    }
                }
            }
        }


        // 获取所有的键值对
        this.entries = function () {
            let result = [];
            for (let row = 0; row < _store.length; row++) {
                if (_store[row] != null) {
                    for (let colum = 0; colum < _store[row].length; colum++) {
                        if (_store[row][colum] != null && _store[row][colum] != null) {
                            result.push(_store[row][colum]);
                        }
                    }
                }
            }
            return result;
        }

        // 获取所有的键
        this.keys = function () {
            let result = [];
            for (let row = 0; row < _store.length; row++) {
                if (_store[row] != null) {
                    for (let colum = 0; colum < _store[row].length; colum++) {
                        if (_store[row][colum] != null && _store[row][colum] != null) {
                            result.push(_store[row][colum].key);
                        }
                    }
                }
            }
            return result;
        }

        // 获取所有的值
        this.values = function () {
            let result = [];
            for (let row = 0; row < _store.length; row++) {
                if (_store[row] != null) {
                    for (let colum = 0; colum < _store[row].length; colum++) {
                        if (_store[row][colum] != null && _store[row][colum] != null) {
                            result.push(_store[row][colum].val);
                        }
                    }
                }
            }
            return result;
        }

    }
}


/**
 * 哈希算法的目标：确定性，效率高，均匀分布。
 *
 * 使用大质数作为模数，可以最大化地保证哈希值的均匀分布
 *
 */

/**
 * 加法哈希
 * 对输入的每个字符的ascii码进行相加，将得到的总和作为哈希值
 * @param key 键
 */
function addHash(key) {
    let hash = 0;
    const modulus = 1000000007;
    for (var i = 0; i < key.length; i++) {
        hash = (hash + key.charCodeAt(i)) % modulus;
    }
    return hash;
}

/**
 * 乘法哈希
 * 每轮乘以一个常数，将各个字符的ascii码累计到哈希值中
 * @param key 键
 */
function mulHash(key) {
    let hash = 0;
    const modulus = 1000000007;
    for (var i = 0; i < key.length; i++) {
        hash = (31 * hash + key.charCodeAt(i)) % modulus;
    }
    return hash;
}

/**
 * 异或哈希
 * 将输入元素的每一个元素通过异或操作累积到一个哈希值中
 * @param key 键
 */
function xorHash(key) {
    let hash = 0;
    const modulus = 1000000007;
    for (var i = 0; i < key.length; i++) {
        hash = hash ^ key.charCodeAt(i);
    }
    return hash & modulus;
}

/**
 * 旋转哈希
 * 将每个字符的ascii码累计到一个哈希值中，每次累积之前都会对哈希值进行旋转操作
 * @param key 键
 */
function rotHash(key) {
    let hash = 0;
    const modulus = 1000000007;
    for (var i = 0; i < key.length; i++) {
        hash = ((hash << 4) ^ (hash >> 28) ^ key.charCodeAt(i)) % modulus;
    }
    return hash;
}